package org.xingole.leetcode.dp.knapsack;

import java.util.Arrays;

/*
 * Problem:
 * 
 * There is a pizza with 3n slices of varying size, you and your friend will take slice
 * of pizza as follows:
 * 
 * - You will pick any pizza slice.
 * - Your friend Alice will pick the next slice in the anti-clockwise direction your pick.
 * - Your freind Bob will pick the next slice in the clockwise direction of your pick.
 * - Repeat until there are no more slices of pizzas.
 * 
 * Given an integer array 'slices' that represent the sizes of the pizza slices in a
 * clockwise diretion, return the maximum possible sum of slice sizes that you can pick.
 *  
 */

public class PizzaWithThreeNSlices {
     /*
      * Overview
      *
      * To approach this problem, we start by recognizing that it is a variation of the 
      * standard dynamic programming problem known as the "House Robber" problem. However,
      * the twist here is that the arrangement of pizza slice is circular.
      *
      * This problem can convert to the following variation:
      * 
      * Given a ring sequence of length 3n, in which you can choose n numbers among which any 
      * two numbers cannot be adjacent, find the maximum sum of these n numbers.
      *
      * Proof
      * We just need to show that any method for selecting n non-adjacent numbers over a ring
      * sequence of length 3n is equivalent to a method for picking a pizza in this problem.
      *
      * Use mathematical induction to show it:
      * 
      * When n = 1, we choose one of the three numbers, since this is a circular sequence, 
      * so after choosing any number, the remaining two numbers will be one either side 
      * of  the selected number, that is, if there are three pizzas, we can choose any one
      * of them.
      * 
      * When n >= 2, there must exist a number 'x' such that two consecutive numbers on
      * on one side of 'x' are not selected ( assuming the interval between all selected 
      * non-adjacent number is 1, that is, only one number in the middle is not selected
      * the the total is 2n, which contradicts the total is 3n). 
      *
      * Without loss of generally, let us assume that there are two consecutive numbers 
      * to the left of 'x' that are not selected, and that there is at least one number 
      * to the right of 'x' that is not selected (otherwise 'x' and the number to its right
      * are adjacent), that is 
      *        ..., ?, 0, 0, x, 0, ?, ...
      * where 0 represents not selected number, ? represents unknown seleted or not number.
      *
      * We delete 'x' and the numbers on both sides,and we get:
      *        ..., ?, 0, ?, ...
      * A ring sequence of length 3n is turned into a ring sequence of length 3(n-1),
      * and the number of n - 1 in the ring sequence is selected, and any two of the selected
      * numbers are not adjacent. In the case of pizza, we pick an unknown pizza for x, and
      * Alice and Bob pick two adjacent pizzas. In this way, we reduce the size of problem
      * from n to n-1.
      *
      */

     /**
      * Approach : Dynamic Programming
      *
      * In a standard "House Robber" problem, you are trying to maximize the amount 
      * you rob from a line of houses without robbing two adjacent houses. However,
      * the pizza is circular, we have to prevent picking adjacent slices, and our 
      * choices wraps around the circle.
      *
      * A key insight is that once we pick the first slice, the circular arrary problem
      * reduces to two separate "House Robber" problems:
      *
      * - One in which the first slice is included and the last slice is excluded, varying
      * the position of the first slice.
      * - Another in which the first slice is excluded and the last slice is included.
      * 
      * 1. Determine the subproblem structure.
      *
      * Let dp[i][j] represents the maximum sum we can obtain by considering up to 
      * the i-th pizza slice (0-indexed) and having picked j slices adhering to the 
      * non-adjacent rule.
      *
      * 2. Recursively solve the problem.
      *
      * Base case:
      *   if i < 2 or j = 0, then 
      *        dp[i][j] = 0,                       if j = 0;
      *        dp[i][j] = slice[0],                if i = 0 and j = 1;
      *        dp[i][j] = max(slice[0], slice[1]), if i = 1 and j = 1;
      *        dp[i][j] = -infinity,               if i < 2 and j >= 2;
      * Inductive case:
      *    if i >= 2 and j > 0, for the i-th slice, we have two options: to take itor not. 
      *       1. if we take it, we adds its size to our total and look back two elements 
      *       in the sequence to avoid adjaceny:
      *          dp[i][j] = dp[i - 2][j - 1] + slice[i];
      *       2. if we don't take it, we simply select j numbers from first i - 1 numbers.
      *           dp[i][j] = dp[i - 1][j]
      *     dp[i][j] = max(dp[i-2][j-1]+slice[i], dp[i-1][j])
      *
      * 
      */
     private static final int NEG_INF = Integer.MIN_VALUE;

     public int maxSizeSlices(int[] slices) {
          // Initialize an array to store slices without the first element
          int[] slicesWithoutFirst = new int[slices.length - 1];
          System.arraycopy(
               slices, 1, 
               slicesWithoutFirst, 0, 
               slicesWithoutFirst.length
          );
          int maxSumExcludingFirst = calculate(slicesWithoutFirst);

          int[] slicesWithoutLast = new int[slices.length - 1];
          System.arraycopy(
               slices, 0, 
               slicesWithoutLast, 0, 
               slicesWithoutLast.length
          );
          int maxSumExcludingLast = calculate(slicesWithoutLast);

          // Return the maximum sum of two cases ( excluding the first slice or the last slice)
          return Math.max(maxSumExcludingFirst, maxSumExcludingLast);

     }

     private int calculate(int[] slices) {
          int N = slices.length;
          int n = (N + 1) / 3;
          
          int[][] dp = new int[N][n+1];

          for ( int i = 0; i < N; i++ ) {
               Arrays.fill(dp[i], NEG_INF);
          }

          // base case:
          dp[0][0] = 0;
          dp[0][1] = slices[0];
          dp[1][0] = 0;
          dp[1][1] = Math.max(slices[0], slices[1]);
          
          // bottom-to-up style
          for ( int i = 2; i < N; i++ ) {
               dp[i][0] = 0;
               for ( int j = 1; j <= n; j++ ) {
                    // constraint: 1 <= slice[i] <= 1000
                    // dp + slice > NEG_INF
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-2][j-1] + slices[i]);
               }
          }

          return dp[N - 1][n];
     }

     public static void main(String[] args) {
          
          PizzaWithThreeNSlices pwns = new PizzaWithThreeNSlices();

          int[] slices; 

          // Example 1:
          // Input: slices = [1, 2, 3, 4, 5, 6]
          // Exceted: 10
          slices = new int[]{1, 2, 3, 4, 5, 6};
          System.out.println("\nExample 1 Output: " + pwns.maxSizeSlices(slices) );

          // Example 2:
          // Input: slices = [8, 9, 8, 6, 1]
          // Excepted: 16
          slices = new int[]{8, 9, 8, 6, 1};
          System.out.println("Example 2 Output: " + pwns.calculate(slices) );
     }
}
